\documentclass[a4paper,11pt]{report}
 
 \usepackage[utf8]{inputenc}
 \usepackage{amssymb,amsmath,amsfonts}
\usepackage{tikz}
\usepackage{graphics}
\usetikzlibrary{arrows}
 %\pagestyle{headings} %les includes
 
 
\newlength{\larg}
\setlength{\larg}{14.5cm} %on defini un type de taille
 
 
 
 
 \title{ % la page de garde
    {\rule{\larg}{1mm}}\vspace{7mm}
	\begin{center}
	  \Huge {\bf {Rapport}} \\ Algorithme \\ Complexité \\ Calculabilité \\
	\end{center}
    }
\author{\begin{tabular}{p{13.7cm}}
Maurin Benjamin, Giner Steve , Perret du Cray Henri
\end{tabular}\\
\hline }
\date{}
 
 \renewcommand{\contentsname}{Table des matières : } % changer le titre de la table des matières

 
 %%%% Redefini le style des titres de chapitre %%%%
\makeatletter
\def\@makechapterhead#1{%
  \vspace*{30\p@}%
  {\parindent \z@ \raggedright \normalfont
    \interlinepenalty\@M
    \ifnum \c@secnumdepth >\m@ne
        \Huge\bfseries \thechapter\quad
    \fi
    \Huge \bfseries #1\par\nobreak
    \vskip 40\p@
  }}
 
 
 % \begin{itemize}
	 % \item bla bla 1
	%  \item bla bla 2
	%  \end{itemize}
 
 

 \begin{document}


\maketitle % la page de garde

  \tableofcontents % la table des matieres 

    \chapter{Partie théorique}
 
    \section{Algorithme}
    \subsection{Exercice 1}
\subsubsection{1)}
			\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,
  thick,main node/.style={circle,draw,minimum size=15pt,font=\sffamily\small}]

  \node[main node] (1) {1};
  \node[main node] (2) [below of=1] {2};
  \node[main node] (3) [right of=2] {3};
  \node[main node] (4) [right of=1] {4};
	\node[main node] (5) [right of=4] {5};
	\node[main node] (6) [right of=3] {6};

  \path[every node/.style={font=\sffamily\small}]
    (1) edge [blue] node {} (4)
        edge [red] node {} (3)
        edge [green] node {} (2)
    (2) edge [green] node {} (3)
    (3) edge [green] node {} (6)
        edge [red] node {} (4)
    (4) edge [blue] node {} (5)
        edge [red] node {} (6)
    (5) edge [blue] node {} (6);
\end{tikzpicture}\\
			Il existe 3 chemins d'arcs-disjoints allant de s à t (voir figure ci dessus).\\
			Comme il n'y a que 3 arcs sortant de s, ce nombre est le nombre maximum.
			\subsubsection{2)}
			
			\begin{tabular}{|c|c|c|c|} \hline
						S & $\bar{S}$& Arcs avants & Arcs arrières \\ \hline
						$1$ & $2,3,4,5,6$ & $(1,4) (1,3) (1,2)$ &  \\ \hline
						$1,2$ & $3,4,5,6$ & $(1,4) (1,3) (2,3)$ &  \\ \hline
						$1,3$ & $2,4,5,6$ & (1,2) (1,4) (3,4) (3,6) & (2,3) \\ \hline
						$1,4$ & $2,3,5,6$ & (1,2) (1,3) (4,5) (4,6) & (3,4) \\ \hline
						$1,5$ & $2,3,4,6$ & (1,2) (1,3) (1,4) (5,6) & (4,5) \\ \hline
						$1,2,3$ & $4,5,6$ & (1,4) (3,4) (3,6) &  \\ \hline
						$1,2,4$ & $3,5,6$ & (1,3) (2,3) (4,5) (4,6) & (3,4) \\ \hline
						$1,2,5$ & $3,4,6$ & (1,3) (1,4) (2,3) (5,6) & (4,5) \\ \hline
						$1,3,4$ & $2,5,6$ & (1,2) (3,6) (4,5) (4,6) & (2,3) \\ \hline
						$1,3,5$ & $2,4,6$ & (1,2) (1,4) (3,4) (3,6) (5,6) & (2,3) (4,5) \\ \hline
						$1,4,5$ & $2,3,6$ & (1,2) (1,3) (4,6) (5,6) & (3,4) \\ \hline
						$1,2,3,4$ & $5,6$ & (3,6) (4,5) (4,6) &  \\ \hline
						$1,2,3,5$ & $4,6$ & (1,4) (3,4) (3,6) (5,6) &  (4,5)\\ \hline
						$1,2,4,5$ & $3,6$ & (1,3) (2,3) (4,6) (5,6) &  (3,4)\\ \hline
						$1,3,4,5$ & $2,6$ & (1,2) (3,6) (4,6) (5,6) &  (2,3)\\ \hline
						$1,2,3,4,5$ & $6$ & (3,6) (4,6) (5,6) &  \\ \hline
			\end{tabular}
			\subsubsection{3)}
			D'après le tableau de la question 2,  le nombre minimum d'arcs avants dans une s-t coupe est égal à 3.\\
Il est donc bien égal au nombre maximum d'arcs-disjoints allant de s à t.

 \subsection{Exercice 2}
      
      \subsubsection{1)}
	  Si on supprime un arc (ij) tel que f(i,j) = 0 , alors on perd un flot de 0. On ne peut pas perdre moins que 0, donc (ij) est un least vital arc.
	 \subsubsection{2)}
	 Appelons f* un flot maximum. \\
	 Montrons : \\
	 (ij) est un Least vital arc $\longrightarrow$ f(i,j) est la valeur minimum de f* : \\
	 Supposons $\exists$ a1 un Least vital arc tel que a1 $\neq$ $\min$(f*). Alors $\exists$ a2 un arc tel que f*(a2)$<$f*(a1).
	 Donc si on supprime a2, f* perd f*(a2), alors que f* perd f*(a1) si on supprime a1. Comme f*(a2)$<$f*(a1), a1 n'est pas un least vital arc. Impossible (hypothèse), donc l'implication est vraie. \\
	 Montrons : \\
	 f(i,j) est la valeur minimum de f* $\longrightarrow$ (ij) est un Least vital arc : \\
	 $\forall$arc a tel que a $=$ $\min$(f*), si on supprime a, f*(a) est supprimé de f*. Comme a est un least vital arc, $\nexists$ a2 tel que f*(a2)$<$f*(a), 
	 donc $\nexists$ d'arc qui enleve plus de flot que a lorsqu'il est supprimé.
	 Donc a est un least vital arc. 
       \subsubsection{3)}
       LVA $=$ least vital arc. \\
       Soit C1 une coupe min. On sait que les arc de C1 sont saturé dans f*.
       Donc les arcs entrant ou sortant des extremités des arcs de C1 ont forcement un flot dans f* inferieur ou égal à l'arc duquel il rentre ou sort de C1.
       Or un f*(LVA) $=$ $\min$(f*), donc un LVA $\notin$ C1 puisque un de ses arcs sortant ou entrant a une valeure inferieure. \\
       
       
  \subsection{Exercice 3}
  On considère le graphe complet $K_{2n+1}$.
	
	\begin{itemize}
		\item Soit $M=\left\{(x_{1},y_{1}),...,(x_{n},y_{n})\right\}$ le couplage maximum de poids minimum de $K_{2n+1}$.\\
		Montrons qu' à partir de M, on peut construire la double étoile de poids minimum de $K_{2n+1}$ par une transformation polynomiale.\\
		Principe: on va construire $2n+1$ doubles étoiles ($2n+1$ centres différents) et regarder laquelle et de poids minimum. Cette transformation reste polynomiale ($O(n^{2})$).\\
		Notons $z$ le sommet qui n'appartient pas au couplage.
		\begin{itemize}
			\item On construit la double étoile de centre $c=z$:\\
			Prendre toute les arêtes de M. Puis,\\
			$\forall i=[1..n]$, si $c(z,x_{i})<c(z,y_{i})$ ajouter $(z,x_{i})$\\
			sinon ajouter $(z,y_{i})$
			\item $\forall i=[1..n]$, on construit la double étoile de centre $c=x_{i}$\\
			Prendre toute les arêtes de M. Puis,\\
			ajouter $(z,y_{i})$, puis\\
			$\forall j\neq i]$, si $c(x_{i},x_{j})<c(x_{i},y_{j})$ ajouter $(x_{i},x_{j})$\\
			sinon ajouter $(x_{i},y_{j})$
			\item $\forall i=[1..n]$, on construit la double étoile de centre $c=x_{i}$\\
			idem que le cas précédent en inversant les rôles de \textit{x} et \textit{y}
		\end{itemize}
		On regarde laquelle de ces $2n+1$ étoiles est de poids minimum: c'est la double étoile de poids minimum de $K_{2n+1}$.
		\item Soit $D=\left\{(a_{1},b_{1}),(b_{1},c)...,(a_{n},b_{n}),(b_{n},c))\right\}$ la double étoile de poids minimum de $K_{2n+1}$.
		Montrons qu' à partir de D, on peut construire le couplage maximum de poids minimum de $K_{2n+1}$ par une transformation polynomiale.\\
		On calule l'indice $i_{0}$ du $max\left\{(c(a_{i},b_{i})-c(b_{i},c)) | i=[1..n]\right\}$
		\begin{itemize}
			\item si le maximum est négatif ou nul:\\
			$\forall i=[1..n]$, on ajoute $(a_{i},b_{i})$ à M
			\item si le maximum est positf:\\
			on ajoute $(b_{i_{0}},c)$ à M\\
			$\forall i\neq i_{0}$, on ajoute $(a_{i},b_{i})$ à M
		\end{itemize}
		Le couplage M obtenu est bien maximum (de taille $n$) et comme la double étoile D est de poids minimum, M sera maximum de poids minimum.\\
		Par ailleurs la transformation considérée est clairement polynomial ($O(n)$).
	\end{itemize}
	On a donc montré l'équivalence entre un problème de double étoile de poids minimum et un problème de couplage maximum de poids minimum dans $K_{2n+1}$.\\
	
 \subsection{Exercice 4}

 \subsubsection{1)}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,
  thick,main node/.style={circle,draw,minimum size=15pt,font=\sffamily\small}]

  \node[main node] (s) {s};
  \node[main node] (b) [below of=s] {b};
  \node[main node] (c) [right of=b] {c};
  \node[main node] (a) [right of=s] {a};
	\node[main node] (d) [right of=a] {d};
	\node[main node] (p) [right of=c] {p};

  \path[every node/.style={font=\sffamily\small}]
    (s) edge node {3} (a)
        edge node {3} (b)
        edge node {2} (c)
    (a) edge node {4} (d)
    (b) edge node {1} (c)
        edge [bend right] node [below] {2} (p)
    (c) edge node {1} (d)
				edge node {1} (a)
        edge node {2} (p)
    (d) edge node {1} (p);
\end{tikzpicture}

\begin{itemize}
	\item $c=4,\Delta=4$ \\
	pas de chemin de $\delta >=4$  
	\item $\Delta=2$ \\
	s,b,p chemin de $\delta=2$ \\
	$f(s,b)=f(b,p)=2$ \\
	mise à jour du graphe d'écart:\\
	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,
  thick,main node/.style={circle,draw,minimum size=15pt,font=\sffamily\small}]

  \node[main node] (s) {s};
  \node[main node] (b) [below of=s] {b};
  \node[main node] (c) [right of=b] {c};
  \node[main node] (a) [right of=s] {a};
	\node[main node] (d) [right of=a] {d};
	\node[main node] (p) [right of=c] {p};

  \path[every node/.style={font=\sffamily\small}]
    (s) edge node {3} (a)
        edge node {1} (b)
        edge node {2} (c)
    (a) edge node {4} (d)
    (b) edge node {1} (c)
        edge [bend left] node {2} (s)
    (c) edge node {1} (d)
				edge node {1} (a)
        edge node {2} (p)
    (d) edge node {1} (p)
		(p) edge [bend left] node [below] {2} (b);
\end{tikzpicture}\\
	s,c,p chemin de $\delta=2$ \\
	$f(s,c)=f(c,p)=2$ \\
	mise à jour du graphe d'écart:\\
	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,
  thick,main node/.style={circle,draw,minimum size=15pt,font=\sffamily\small}]

  \node[main node] (s) {s};
  \node[main node] (b) [below of=s] {b};
  \node[main node] (c) [right of=b] {c};
  \node[main node] (a) [right of=s] {a};
	\node[main node] (d) [right of=a] {d};
	\node[main node] (p) [right of=c] {p};

  \path[every node/.style={font=\sffamily\small}]
    (s) edge node {3} (a)
        edge node {1} (b)
    (a) edge node {4} (d)
    (b) edge node {1} (c)
        edge [bend left] node {2} (s)
    (c) edge node {1} (d)
				edge node {1} (a)
				edge node {2} (s)
    (d) edge node {1} (p)
		(p) edge [bend left] node [below] {2} (b)
				edge node {2} (c);
\end{tikzpicture}\\
	plus d'autre chemin de $\delta >=2$ 
	\item $\Delta=1$ \\
	s,a,d,p chemin de $\delta=1$ \\
	$f(s,a)=f(a,d)=f(d,p)=1$ \\
	mise à jour du graphe d'écart:\\
	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,
  thick,main node/.style={circle,draw,font=\sffamily\small}]

  \node[main node] (s) {s};
  \node[main node] (b) [below of=s] {b};
  \node[main node] (c) [right of=b] {c};
  \node[main node] (a) [right of=s] {a};
	\node[main node] (d) [right of=a] {d};
	\node[main node] (p) [right of=c] {p};

  \path[every node/.style={font=\sffamily\small}]
    (s) edge node {2} (a)
        edge node {1} (b)
    (a) edge node {3} (d)
				edge [bend right] node [above] {1} (s)
    (b) edge node {1} (c)
        edge [bend left] node {2} (s)
    (c) edge node {1} (d)
				edge node {1} (a)
				edge node {2} (s)
    (d) edge [bend right] node [above] {1} (a)
		(p) edge [bend left] node [below] {2} (b)
				edge node {2} (c)
				edge node {1} (d);
\end{tikzpicture}\\
	plus d'autre chemin de $\delta >=1$ 
	\item $\Delta=0, \Delta<1$ \\
	fin de l'algorithme. 
\end{itemize}
	\subsubsection{2)}
	a. Par l'absurde, si t appartenait à S, il existerait un chemin dans G(f',Delta), donc on pourrait augmenter f'.\\
Or, f' est maximal (Si on est arrivé à la fin d'une phase c'est qu'on ne peut plus augmenter f').\\
Absurde, donc t n'appartient pas à S.\\
On peut donc définir la coupe $[S,\bar{S}]$.\\
\\
	b. $R[S,\bar{S}]=\sum_{(i,j)\in[S,\bar{S}]}r_{ij}$ \\
	$\forall(i,j), r_{ij}\leq\Delta$ \\
	Donc $R[S,\bar{S}]\leq m\Delta$ \\
	On en déduit $C(S,\bar{S})\leq m\Delta$ à la fin d'une phase($\Delta$ fixé)\\
	\\
	c. Théorème: \textit{Pour n'importe quel flot f de valeur $|f|$ dans le réseau, le flot additionnel qui peut circuler de s à t est inférieur ou égal à la capacité résiduelle de toute s-t coupe. } \\
	On en déduit $f^{*}-f'\leq m\Delta$ \\
	\\
	d. A la phase suivante, la quantité de flot transporté à chaque augmentation est supérieure ou égale à $\Delta/2$ (et inférieure à $\Delta$). \\
	Comme $f^{*}-f'\leq m\Delta$, \\
	nombre d'augmentations $\leq \frac{f^{*}-f'}{\Delta/2}$ \\
	nombre d'augmentations $\leq 2m$ (d'après c.) 
	\subsubsection{3)}
	Il y a $\left\lfloor log  C \right\rfloor$ phases. ($log (2^{\left\lfloor log  C\right\rfloor}$))
	\subsubsection{4)}
	D' après les deux questions précédentes:\\
	nombre total d'itérations $\leq 2m\left\lfloor log  C\right\rfloor$\\
	nombre total d'itérations $=\textit{O}(m\cdot log  C)$ \\
	Complexité de chaque itération: identification d'un chemin améliorant: \textit{O}(m). \\
	Donc l'algorithme admet une complexité en $\textit{O}(m^{2}\cdot log  C)$.

\section{Complexité}
 \subsection{Exercice 5}
 \subsubsection{1)}
	a. SAT:
	\begin{tabbing}
	\hspace{1.7cm} \= \\
	Données:
	\> 		V un ensemble de variables $(v_{1}, ... ,v_{n})$\\
	\> 		C un ensemble de clauses $(c_{1}, ... , c_{m})$\\
	\>		(où chaque $c_{i}$ est une disjonction de littéraux $l_{j}, \exists k\in[1..n], l_{j}=v_{k} ou l_{j}=\bar{v_{k}}$\\
	Question:
	\>		Existe-t-il une affectation des variables de V rendant l'ensemble des clauses vraies \\
	\>		(satisfaisant l'ensemble des clauses)?
	\end{tabbing}
	
	3-SAT: même énoncé que SAT avec uniquement des clauses de taille 3.\\
	\\
	b. Une réduction est une transformation consistant à faire correspondre une instance d'un problème à une instance particulière d'un autre problème. Elle est dite polynomiale si la transformation est polynomiale en la taille du problème.\\
	\\
	c. 
	\begin{itemize}
		\item 3-SAT est dans NP
		\item Pour montrer que 3-SAT est NP-Complet montrons qu'on peut réduire polynomialement SAT à 3-SAT:\\*
		
		\begin{itemize}
			\item \emph{clauses de taille 2}:\\
			Soit $C=l_{1}\vee l_{2}$\\
			On transforme C en 2 clauses de taille 3:\\
			$C_{1}=l_{1}\vee l_{2}\vee t$\\
			$C_{2}=l_{1}\vee l_{2}\vee \neg t$\\
			Si C est vraie, $C_{1}$ et $C_{2}$ sont vraies.\\
			Et si $C_{1}$ et $C_{2}$ sont vraies, C est vraie.\\
			\item \emph{clauses de taille 1}:\\
			Soit $C=l$\\
			On transforme C en 4 clauses de taille 3:\\
			$C_{1}=l\vee u\vee t$\\
			$C_{2}=l\vee u\vee \neg t$\\
			$C_{3}=l\vee \neg u\vee t$\\
			$C_{4}=l\vee \neg u\vee \neg t$\\
			Si C est vraie, $C_{1}$, $C_{2}$ $C_{3}$ et $C_{4}$ sont vraies.\\
			Et si $C_{1}$, $C_{2}$ $C_{3}$ et $C_{4}$ sont vraies, C est vraie.\\
			\item \emph{clauses de taille $n\geq 3$}:\\
			Montrons par récurrence \textit{$H_{n}$}:"Toute clause de taille n peut être réduite polynomialement à la conjonction de (n-2) clauses de taille 3" pour $n\geq 3$.\\
			\textit{$H_{3}$} est vraie: 1 clause de taille 3.
			Supposons \textit{$H_{n}$}, $n\geq 3$.\\
			Soit C une clause de taille n+1.
			$C=l_{1}\vee l_{2} \vee ... \vee l_{n+1}$\\
			On transforme C en une clause de taille 3 et une clause de taille n:\\
			$C_{1}=l_{1}\vee l_{2}\vee t$\\
			$C_{2}=l_{3}\vee ... \vee l_{n+1}\vee \neg t$\\
			Si il existe une affectation rendant C vraie, \\
			$1^{er}$ cas: $l_{1}\vee l_{2}$ est vrai:\\
			L'affectation rendant en plus t faux satisfait $C_{1}$ et $C_{2}$.\\
			$2^{eme}$ cas: $l_{3}\vee ... \vee l_{n+1}$\\
			L'affectation rendant en plus t vrai satisfait $C_{1}$ et $C_{2}$.\\
			Et si $C_{1}$ et $C_{2}$ sont vraies, C est vraie.\\
			D'après \textit{$H_{n}$}, $C_{2}$ peut se réduire à la conjonction de (n-2) clauses de taille 3.\\
			Donc C peut se réduire à la conjonction de (n-1) clauses de taille 3: \textit{$H_{n+1}$} est vraie.
			Donc $\forall n\geq 3$, Toute clause de taille n peut être réduite polynomialement à la conjonction de (n-2) clauses de taille 3.
		\end{itemize}
		Toute clause d'une instance de SAT se réduit polynomialement à une conjonction de clauses de taille 3.
		On en déduit que SAT se réduit polynomialement à 3-SAT puis que 3-SAT est NP-Complet.
	\end{itemize}
	 d. On a vu ci-dessus que la transformation créait:
	
	\begin{itemize}
		\item Pour chaque clause de taille 1: 4 clauses à 3 littéraux et 2 variables.
		\item Pour chaque clause de taille 2: 2 clauses à 3 littéraux et 1 variable.
		\item Pour chaque clause de taille 4: 2 clauses à 3 littéraux et 1 variable.
		\item Pour chaque clause de taille 5: 3 clauses à 3 littéraux et 2 variables.
	\end{itemize}
	On en déduit que le système obtenu par la réduction contient:\\
	variables: $n_{v}+2n_{1}+n_{2}+n_{4}+2n_{5}$\\
	clauses:  $4n_{1}+2n_{2}+n_{3}+2n_{4}+3n_{5}$
	
	\subsubsection{2)}
	Si on essaye d'appliquer le même principe de réduction pour obtenir une instance de 2-SAT, on se rend vite compte que cela ne fonctionne pas:\\*
	Soit $C=l_{1}\vee l_{2}\vee l_{3}$ une clause de taille 3:
	$C_{1}=l_{1}\vee t$\\
	$C_{2}=l_{2}\vee l_{3}\vee \neg t$\\
	$C_{2}$ est de taille 3: on ne peut pas réduire 3-SAT à 2-SAT par cette méthode.
	
	\subsubsection{3)}
	Appelons pour la suite de cette question 2P1N-SAT le problème SAT où chaque variable est restreinte à apparaître 1 ou 2 fois positivement et 1 fois négativement.\\
	Montrons que 2P1N-SAT est NP-Complet:
	
	\begin{itemize}
		\item 2P1N-SAT appartient à NP: il est facile de vérifier si une solution marche.
		\item Considérons une instance de SAT:\\
		Soit $v$ une variable qui apparaît n fois négativement($n\geq 2$)\\
		Supposons qu'elle apparaisse dans $C_{1}$ et $C_{2}$.\\
		$C_{1}= \neg v \vee C'_{1}$ (où $C'_{1}$ est une clause)\\
		$C_{2}= \neg v \vee C'_{2}$ (où $C'_{2}$ est une clause)\\
		On transforme ces 2 clauses en:\\
		$C_{3}= \neg v \vee \neg t$\\
		$C_{4}= t \vee C'_{1}$\\
		$C_{5}= t \vee C'_{2}$\\
		Si $C_{1}$ et $C_{2}$ vraies:
		\begin{itemize}
			\item $1^{er}$ cas v est vrai: donc $C'_{1}$ et $C'_{2}$ sont vraies\\
			Donc $C_{4}$ et $C_{5}$ sont vraies.\\
			En prennant $t=faux$, $C_{3}$ est vraie.
			\item $2^{eme}$ cas v est faux: $C_{3}$ est vraie.\\
			En prennant $t=vrai$, $C_{4}$ et $C_{5}$ sont vraies.
		\end{itemize}
		Inversement si $C_{3},C_{4}$ et $C_{5}$ sont vraies:
		\begin{itemize}
			\item $1^{er}$ cas t est vrai: v est faux.\\
			Donc $C_{1}$ et $C_{2}$ sont vraies.
			\item $2^{eme}$ cas t est faux: donc $C'_{1}$ et $C'_{2}$ sont vraies.\\
			Donc $C_{1}$ et $C_{2}$ sont vraies.
		\end{itemize}
		t apparaît 2 fois positivement et 1 fois négativement.\\
		v n'apparaît plus que (n-1) fois négativement.\\
		\textit{Remarque: On peut faire exactement la même chose pour une variable qui apparaît n fois positivement ($n\geq 3$)}\\
		En itérant le processus et en l'appliquant à chaque variable, on obtient un ensemble de clauses où chaque variable apparaît au plus 2 fois positivement et 1 fois négativement.\\
		On peut réduire SAT à 2P1N-SAT.\\
	\end{itemize}
	2P1N-SAT est NP-Complet.
  \subsection{Exercice 6}
		\subsubsection{1)}
		
		\begin{itemize}
			\item Si \textit{x} est un sommet isolé et appartient à une \textit{VertexCover(G,k)}, alors il existe une \textit{VertexCover(G,k-1)}.
			\item Soit \textit{x} un sommet de degré 1 et \textit{y} son voisin. Supposons \textit{V} une \textit{VertexCover(G,k)} avec k optimal.\\
			L'arête (\textit{x},\textit{y}) doit être couverte donc:
			
			\begin{itemize}
				\item Soit $y\in V$ et \textit{V} est optimale.
				\item Soit $x\in V$, dans ce cas: $V-\left\} x\right\} +\left\{y\right\}$ est une vertex-cover optimale contenant y.
			\end{itemize}
			\item Soit G possédant une vertex-cover de taille k : $V$\\
			Soit $x$ un sommet de G de degré $d\geq k+1$.\\
			Supposons que $x\notin V$: $V$ est une vertex-cover donc les d voisins de $x$ doivent appartenir à $V$: Absurde ($V$ est de taille k).\\
			Donc  $x\in V$
		\end{itemize}
		
		\subsubsection{2)}
		Le graphe réduit ne contient aucun sommet isolé, aucun sommet de degré 1 ou supérieur à k+1.\\
		a. les sommets de la vertex-cover(k sommets) "voient" toutes les arêtes:\\
		D'où Nombre d'arêtes $\leq k^{2}$ (degré des sommets inférieur à k)\\
		\\
		b. Dans le pire des cas, chacune des arêtes relie un sommet de la vertex-cover a un sommet différent.\\
		On en déduit Nombre de sommets $\leq k+k^{2}$.
		
		\subsubsection{3)}
		Par contraposée de la question 2), si le graphe réduit possède plus de $k+k^{2}$ ou plus de $k^{2}$ arêtes, le graphe n'admet pas de vertex-cover de taille k.
		\subsubsection{4)}
		a. Montrons que l'algorithme est valide:
		\begin{itemize}
			\item les cas d'arrêt sont valides: Si $E(G)=c$ il y a une solution.\\
			Si $k=0$ et $E(G)\neq\emptyset$, il n'y a pas de solution.
			\item cas récursif: Soit $(u,v)\in E(G)$. Notons $G_{1}=G-\left\{u\right\}$ et $G_{2}=G-\left\{v\right\}$.\\
			Montrons que $VC(G,k)=VC(G_{1},k-1)\vee VC(G_{2},k-1)$.\\
			$\Rightarrow $ Supposons que $VC(G,k)=vrai$.\\
			Soit $V$ une vertex-cover de taille k de G. L'arête (u,v) est couverte par $V$:
			\begin{itemize}
				\item Soit $u\in V$, donc $VC(G_{1},k-1)=vrai$
				\item Soit $v\in V$, donc $VC(G_{2},k-1)=vrai$
			\end{itemize}
			$\Leftarrow$ Supposons que $VC(G_{1},k-1)\vee VC(G_{2},k-1)=vrai$
			\begin{itemize}
				\item $1^{er}$ cas $VC(G_{1},k-1)=vrai$:\\
				$\exists V_{1}$ une vertex-cover de taille k-1 de $G_{1}$\\
				$V=V_{1}+\left\{u \right\}$ est une vertex-cover de taille k de G.\\
				$VC(G,k)=vrai$.
				\item $2^{eme}$ cas $VC(G_{2},k-1)=vrai$: raisonnement identique.
			\end{itemize}
		\end{itemize}
		L'algorithme est valide.\\
		\\
		b. Complexité dans le pire cas: $2^{k}$.
		\subsubsection{5)}
		Considérons le graphe G suivant pour $k_{1}=1$ et $k_{2}=2$.\\
		\begin{tikzpicture}[-,>=stealth',shorten >=1pt,auto,node distance=1.5cm,
  thick,main node/.style={circle,draw,minimum size=15pt,font=\sffamily\small}]

  \node[main node] (1) {1};
  \node[main node] (2) [right of=1] {2};
  \node[main node] (3) [below of=1] {3};
  \node[main node] (4) [right of=3] {4};

  \path[every node/.style={font=\sffamily\small}]
    (1) edge node {} (2)
        edge node {} (3)
    (2) edge node {} (3)
    (3) edge node {} (4)
    (4) edge node {} (2);

\end{tikzpicture}
		
		\begin{itemize}
			\item on choisit l'arête (1,2).\\
			on note G$_{1}$=G-$\left\{1\right\}$ et G$_{1}$=G-$\left\{1\right\}$\\
			on appelle $VC(G_{1},k-1) (k=k_{1}$ ou $k_{2})$\\
			$E(G_{1})\neq \emptyset$
			\begin{itemize}
				\item cas 1: $k_{1}-1=0$ retourner faux\\
					on appelle $VC(G_{2},0)$, $E(G_{2})\neq \emptyset$, on retourne faux\\
					l'algorithme retourne faux.\\
				\item cas 2: $k_{2}-1=1$: on choisit l'arête (3,4).\\
				on note G$_{11}$=G$_{1}$-$\left\{3\right\}$ et G$_{12}$=G$_{1}$-$\left\{4\right\}$\\
				on appelle $VC(G_{11},0)$\\
				$E(G_{11})\neq \emptyset$, on retourne faux.\\
				on appelle $VC(G_{12},0)$\\
				$E(G_{12})\neq \emptyset$, on retourne faux.\\
				on appelle $VC(G_{2},1)$: 
				$E(G_{2})\neq \emptyset$, on choisit l'arête (3,4).\\
				on note G$_{21}$=G$_{2}$-$\left\{3\right\}$ et G$_{22}$=G$_{2}$-$\left\{4\right\}$\\
				on appelle $VC(G_{11},0)$\\
				$E(G_{11})= \emptyset$, on retourne vrai.\\
				l'algorithme retourne vrai.\\
			\end{itemize}
			
		\end{itemize}
		
\section{Calculabilité}

 \subsection{Exercice 7}
  \subsubsection{1)}
  $\forall$ (x,y) $\in \mathbb{N} \times \mathbb{N}$, on trie (x$+$y) par ordre lexicographique. Ainsi, tous les couples d'entiers sont énumérés.
  on a alors couple(x,y) = $\frac{(x+y)(x+y+1)}{2}$+y .
  \subsubsection{2)}
  Soit z$\in\mathbb{Z}$ \\
  Codage : \\ si z$\geq$0 f1(z)$=$2z$=$x sinon f1(z)$=$2z-1$=$x \\
  Decodage : \\ si z impair f2(z) $= \frac{-(z+1)}{2} =$ y sinon f2(z) $= \frac{z}{2} =$ y
  \subsubsection{3)}
  Triplet : \\ h(x,y,z)$=$couple(x,couple(y,z)) \\
  k-uplets : \\ h(x1,x2,...,xk)=couple(x1,couple(x2,couple(x3, ... couple(xk-1,xk) ))
  \subsubsection{4)}
  Supposons l'intervalle [0,1] dénombrale : \\
  x1 $=$ 0, $x_{1}^{1}$  $x_{2}^{1}$  $x_{3}^{1}$ ... $x_{n}^{1}$ \\
  x2 $=$ 0, $x_{1}^{2}$  $x_{2}^{2}$  $x_{3}^{2}$ ... $x_{n}^{2}$ \\
  ... \\
  xp $=$ 0, $x_{1}^{p}$  $x_{2}^{p}$  $x_{3}^{p}$ ... $x_{n}^{p}$ \\
  \\ Soit vi $=$ $x_{i}^{i}$ + 1 \\
  Alors 0,v1v2v3 ... est dans la liste, et on a donc $x_{m}^{m}$ $=$ $x_{m}^{m}$ + 1 : Absurde. \\
  Donc l'intervalle [0,1] n'est pas dénombrale.
  
  \subsection{Exercice 8}
 \subsubsection{1)}
  On s'intéresse aux fonctions définies sur l'ensemble  des entiers naturels.
  On construit les fonctions récursives primitives de proche en proche en partant des trois fonctions de base :
  \begin{itemize}
	  \item La fonction identiquement nulle
	  \item La fonction Successeur Succ(t) $=$ t + 1
	  \item Les projections (x1,x2,...,xk) $\longrightarrow$ xi
  \end{itemize} 

Et en itérant la construction suivante : \\ 
	 \hspace{0.5cm} La composition de fonctions : si f1,f2,...,fk  sont récursives primitives sur $\mathbb{N}$ et si h est récursive primitive sur $\mathbb{N}$, toutes déjà définies,
	alors la fonction  \hspace{0.5cm}  g $=$ h(f1,f2,...,fk) est une nouvelle fonction récursive primitive.
\subsubsection{2)}
Un ensemble est recursif primitif si sa fonction caractéristique est recursive primitive.
\subsubsection{3)}
\begin{tabbing}
   \hspace{0.5cm} \= \\
\>(a) Somme(0,x) $=$ x \\
\>Somme(Succ(x),y) $=$ Succ(Somme(x,y))\\ \\
\>(b) Produit(0,y) $=$ 0 \\
\>Produit(Succ(x),y)= Somme (y,Produit(x,y)) \\ \\
\>(c) exp(0,y) $=$ 0 \\
\> exp(Succ(x),y) $=$ Produit(y,exp(x,y)) \\ \\
\>(d) MoinsUn(0) $=$ 0\\
\>  MoinsUn(Succ(x))=x \\ \\
\>(e)Soustraction(x,0) $=$ x\\
\> Soustraction(0,y) $=$ 0 \\
\> Soustraction(x,y) $=$ Soustraction(MoinsUn(x),MoinsUn(y)) \\ \\
\>(f) sg(0) $=$ 0\\
\> sg(x) $=$ 1 \\ \\
\>(g) Soit p la fonction caractéristique de x$>$y \\
\> p(x,y) $=$ sg(Soustraction(x,y)) \\ \\
\> Soit p' la fonction caractéristique de x$\geq$y \\
\> p'(x,0) $=$ 1  p'(0,y) $=$ 0 p'(0,0) $=$ 1 \\
\> p'(x,y) $=$ p'(MoinsUn(x),MoinsUn(y)) \\ \\
\>(h) Soit $f_{A}$ la fonction caractéristique de A \\
\> h(x1,x2,...,xn) $=$ Somme(Produit($f_{A}$(x1,x2,...,xn),f(x1,x2,...,xn)),\\ \> Produit(Soustraction(1,$f_{A}$(x1,x2,...,xn)),g(x1,x2,...,xn)) \\
\end{tabbing}

 \chapter{Partie Pratique}
\section{Le langage C++}

Nous avons choisi ce langage de programmation pour différentes raisons.\\ Tout d'abord, c'est un langage compilé. Il est bien plus rapide qu'un langage interprété ou semi-interprété comme le Java.\\
Ensuite, le C++ nous permet d'utiliser des librairies et donc des raccourcis de programmation nous permettant de nous focaliser sur les exercices du TP et non sur la complexité d'algorithme plus classique comme ceux de tri par exemple.\\
Pour finir, c'est un langage que nous avons tous étudié à l'université et nous l'avons choisi pour ne pas être contraint par l'apprentissage du langage.


 \section{Les structures de données}

%\vspace{9cm}
	\includegraphics[scale=0.5]{structure_graphe.jpg}

Le graphe tout comme le graphe d’écart ou de couche est représenté par un par un vecteur de vecteur de vecteur d’entier ( $vector$$<$$vector$$<$$vector$$<$$int$$>$ $>$ $>$ $G$ ).\\
Les sommets sont représentés par des entier allant de 0 à $n-1$, 0 étant la source et $n-1$ le puit.\\
Le premier vector est de taille $n$ (nombre de sommet du graphe). En l’indice $i$, on a le vector d’arêtes du sommet $i$. Ce vector étant lui-même un vector d’entier contenant le sommet d’arrivée de l’arête, son flot et sa capacité. Par exemple, si on veut obtenir le flot  d’une arêtes partant du sommet 2 (si elle existe), on fait $G[2][0][1]$.\\

Nous allons dans cette partie expliquer pourquoi nous avons fait le choix de cette structure et des différents objets associés.

 \subsection{Pourquoi la classe $<$vector$>$ ?}
Tout d’abord, un vector est une liste indexé. En effet, il permet d’avoir une taille variable et un accès direct à une donnée d’index $i$. On peut donc l’utiliser comme un tableau classique tout en pouvant ajouter des éléments en temps constant comme dans une liste.\\

Un autre avantage du vector, à la différence d’une matrice par exemple, est qu’il permet de n’avoir que les données nécessaires dans et donc lors d’un parcours des arêtes d’un sommet, faire un parcours de $m$ et non de $n$.\\

Le dernier avantage de cette classe est qu’elle fait partie de la librairie STL. Elle contient donc différentes fonctions, entre autres le tri ($sort()$), déjà développées et fortement optimisées par des gourous de l’informatique. Ceci nous permettant de nous concentrer sur les algorithmes du TP.\\

Le seul défaut du vector dans notre situation est la suppression d’un élément autre que le dernier pour la suppression d’arêtes. En effet, la suppression d’un élément en fin de vector se fait en temps constant par une simple réduction de la taille du vector et un changement de pointeur alors qu’à un autre endroit du vector ceci est en $O$$($$taille$ $du$ $vector$$)$. Mais nous avons réduit ce problème à quelques actions basiques : étant donné que qu’il n’y a pas d’ordre dans notre vector d’arêtes ($G[i]$), nous avons pu échanger le dernier élément du vector avec l’élément que nous voulions supprimer et supprimer le dernier élément du vector ($O(m)\rightarrow O(2)$).\\

 \subsection{Une matrice d’indice}
%\vspace{5cm}
	\includegraphics[scale=0.5]{matrice.png}

Le défaut de cette structure était l'impossibilité d’atteindre en temps constant les données d’une arête. Par exemple, pour obtenir les données de l’arête $2\rightarrow 5$, on devait parcourir tout le vector de l’indice 2 ( $G[2]$ ) ce qui nous donnait un parcours en $O(m)$ et, de plus, on n’avait aucun moyen en temps constant de savoir si l’arête existait.\\
Pour pallier à ce problème nous avons décidé d’utiliser une matrice n * n contenant aux indice i,j l’indice dans le vector G[i] de l’arête $i\rightarrow j$ et une valeur par défaut pour signifier que l’arête n’existe pas (-1). Ce tableau est modifié à chaque ajout et suppression, ce qui ne coûte donc qu’une affectation de plus, chose négligeable comparé au gain occasionné sur l’accès à une arête ($O(m)\rightarrow O(1)$). 

 \section{Les algorithmes}

Les tests ont été effectué sur une machine personnelle avec un core 2 duo cadencé à 2,2 GHz et 4 Go de RAM sous Windows 7. Nous avons pris 4 nombres différents de sommets (50,500,1000,2000). Les arêtes sont ajoutées de manière aléatoire avec 2 probabilités différentes: 
\begin{itemize}
	\item{faible densité : 50\% de chances d'avoir une arêtes entre 2 sommets}
	\item{forte densité : 80\% de chances d'avoir une arêtes entre 2 sommets}
\end{itemize}
Les arêtes ont une capacité comprise entre 1 et 10 (en raison de risque de temps d'exécution beaucoup trop long sur Edmond-Karp ou Ford Fulkerson). 
Chaque sommet a forcément au moins un arête entrante et une arête sortante sauf pour la source et le puit qui ont respectivement que des arêtes sortantes et que des entrantes.//
Les résultats des tests sont des moyennes de plusieurs tests.

\subsection{Edmond Karp}

%\vspace{6cm}
	\includegraphics[scale=0.5]{edmondkarp.png}

Comme on peut le voir sur le graphique, le nombre d'arete du graphe a un fort impact sur le temps d'execution lorsque l'on commence a avoir un nombre de sommet élevé. Le temps d'execution est presque doublé. On peut donc en conclure que c'est un algorithme peu efficace lorsque les chemins de la source au puit sont nombreux.



\subsection{Dinic}

%\vspace{6cm}
	\includegraphics[scale=0.5]{dinic.png}

On remarquera que cet algorithme est beaucoup plus rapide que le précédent (environ 2 fois plus). L'augmentation du temps de calcul en fonction du nombre de sommet est plus lente mais lorsque le graphe a une forte densité on double tout même le temps d'execution par rapport au calcul avec une faible densité. Cet algorithme traite donc mieux la multiplication des chemins qu'Edmond Karp.

\subsection{Ford-Fulkerson}
 
%\vspace{6cm}
	\includegraphics[scale=0.5]{ford.png}

Cet algorithme est assez similaire à Edmond Karp dans sa manière de fonctionner, il souffre donc des mêmes défauts. Il est un peu plus rapide qu'Edmond Karp car il ne passe pas par la graphe d'écart mais reste bien moins rapide que Dinic surtout lorsque l'on augmente le nombre d'arêtes et de sommets. Nos résultats ne sont peut être pas très pertinent car la recherche des prédécesseurs se fait en $O(n)$ et non en $O(m)$ (trouver si un sommet donné est prédécesseur se fait en $O(1)$ grâce à la matrice d'indices)  comme celle des successeurs à cause de notre structure de données utilisée. Pour l'améliorer il aurait fallu créer un vecteur de prédécesseurs associés mais en contrepartie on aurait eu d'autres manipulations bien plus coûteuse comme la création, la modification et les mise à jours du graphe. 

\subsection{Capacity Scaling}

%\vspace{6cm}
	\includegraphics[scale=0.5]{capacity.png}

Cette méthode est assez proche de Edmond Karp à la différence que l'on travail sur moins d'arêtes en même temps. En augmentant les capacités max possiblent sur les arêtes, on peut remarquer que cet algorithme résiste mieux que Ford Fulkerson et Edmond Karp.

\subsection{Synthèse}

Pour conclure, on peut dire que l'algorithme qui résiste le mieux à l'augmentation du nombre de sommet et d'arêtes est Dinic. En effet, la récupération d'un ensemble de plus courts chemins permet de considérablement améliorer la complexité du calcul de flot maximum. Les 3 autres algorithme ont des résultats assez similaires, mais il faudrait faire de plus grosses batteries de tests pour pouvoir observer les différences de complexité.
\end{document}